package zhaojin;

import niuke.Bags01;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Created by asus on 2017/12/2.
 */
public class BTM {
    //一些全局的字段，方便记录最优解
    public static int bestvalue = 0;
    public static List<Element> bestchoice = new ArrayList<Element>();
    public static List<Element> foreverBan = new ArrayList<Element>(); //节点永远禁止集(到头或超重时加入)

    //集合交操作
    public static List<Element> diff(List<Element>  ls1, List<Element> ls2) {
        List<Element> list = new ArrayList<Element>(ls1);
        for(Element e1 : ls1)
            for (Element e2 :ls2)
                if(e1.equals(e2))
                    list.remove(e1);
        return list;
    }

    //集合并操作
    public static List<Element> union(List<Element>  ls1, List<Element> ls2){
        List<Element> list1 = new ArrayList<Element>(ls1);
        List<Element> list2 = new ArrayList<Element>(ls2);
        List<Element> list = new ArrayList<Element>();
        for(Element e1 : ls1)
            for (Element e2 :ls2)
                if(e1.equals(e2))
                    list.add(e1);
        list2.removeAll(list);
        list1.addAll(list2);
        return list1;
    }
    //保存现场的筛选法
    public static void cut(Backage backage){
        List<Element> relist = new ArrayList<Element>(foreverBan);
        for(Element element:relist)
            if (element.getId()>backage.getLastElementIdinBackage())
                foreverBan.remove(element);
    }
    //集合回溯法（基于一颗不一样排列的子集树，赵晋想出来的哈哈哈哈哈）
    public static void backTrackingMethod(List<Element> elementlist,Backage backage,List<Element> nowbanlist,List<Element> nowselectablelist){
        nowselectablelist.addAll(diff(elementlist,nowbanlist));
        if(nowselectablelist.size()!=0){//如果当前可选集不为空
            if(backage.getin(nowselectablelist.get(0))){//如果下一个物品未超重，可以装入
                nowbanlist.add(nowselectablelist.get(0));
                nowselectablelist.clear();
                backTrackingMethod(elementlist,backage,nowbanlist,nowselectablelist);
            }
            else {//当前可选不为空，但是超重了
                if(backage.nowvalue()>bestvalue){
                    bestvalue = backage.nowvalue();
                    bestchoice.clear();
                    bestchoice.addAll(backage.getAlreadytakein());
                }
                nowbanlist.add(nowselectablelist.get(0));//将超重到加入ban集
                foreverBan.add(nowselectablelist.get(0));//超重，加入节点永禁
                nowselectablelist.clear();
                //返回上一层继续挑选
                backTrackingMethod(elementlist,backage,nowbanlist,nowselectablelist);
            }
        }
        else{//如果可选集为空
            if(foreverBan.size()==elementlist.size()){
                return;
            }
            else {
                if(foreverBan.get(foreverBan.size()-1).getId()==elementlist.get(elementlist.size()-1).getId())
                    cut(backage);
                //到头or回溯后尽头，加入节点永禁
                if(nowbanlist.size()==elementlist.size()){ //没东西可拿，开始回溯
                    if(backage.nowvalue()>bestvalue){
                        bestvalue = backage.nowvalue();
                        bestchoice.clear();
                        bestchoice.addAll(backage.getAlreadytakein());
                    }
                    nowbanlist.clear();
                    nowbanlist.addAll(union(foreverBan,backage.getAlreadytakein()));  //计算上一节点的禁区
                    cut(backage);
                    foreverBan.add(nowbanlist.get(nowbanlist.size()-1));//记录回溯节点，把它加入永禁集
                    backage.getLastElementOut(); //回溯
                    backTrackingMethod(elementlist,backage,nowbanlist,nowselectablelist);
                }
            }
        }
    }


    //测试部分
    public static void main(String[] args) {
        int num=20;
        Bags01 bags;
        int[] ws=new int[num];
        int[] vs=new int[num];
        List<Element> elementlist = new ArrayList<Element>();
       // Backage backage = new Backage(300);
        List<Element> nowbanlist = new ArrayList<Element>();
        List<Element> nowselectablelist = diff(elementlist,nowbanlist);
        Random r;
        for(int i=0;i<num;i++){
            r=new Random(new Random().nextInt());
            int w=r.nextInt(310);
            int v=r.nextInt(300);
            ws[i]=w;
            vs[i]=v;
            elementlist.add(new Element(i,w,v));
        }
        for(int i=0;i<num;i++){
            System.out.println("weight="+ws[i]+"  value="+vs[i]);
        }
        double[] temp=new double[num];
        for(int i=0;i<num;i++){
            temp[i]=vs[i]/(ws[i]*1.0);
            System.out.print(temp[i]+" ");
        }
        System.out.println();
        long startTime1=System.nanoTime();   //获取开始时间
        for (int i = 0;i <num;i++){
            for(int j = i;j <num;j++){
                if (temp[i] < temp[j]){
                    double a = temp[i];
                    temp[i]=temp[j];
                    temp[j]=a;
                    int t = ws[i];
                    ws[i]=ws[j];
                    ws[j]=t;
                    int y=vs[i];
                    vs[i]=vs[j];
                    vs[j]=y;
                }
            }
        }
        bags=new Bags01(ws,vs);
//        for(int i=0;i<num;i++){
//            System.out.println("weight="+ws[i]+"  value="+vs[i]);
//        }

//        long startTime=System.nanoTime();   //获取开始时间
//
//        backTrackingMethod(elementlist,backage,nowbanlist,nowselectablelist);
//
//        long endTime=System.nanoTime(); //获取结束时间
//        System.out.println("程序运行时间： "+(endTime-startTime)+"ns"+"   ， "+(endTime-startTime)/1000000+"ms");
//
//        System.out.println("背包容量为："+backage.getCapacity());
//        System.out.println("最优解为：");
//        for(Element element :bestchoice){
//            System.out.println(element.toString());
//        }
//        System.out.println("最优解的价值为："+bestvalue+"\n\n");

//        long startTime1=System.nanoTime();   //获取开始时间
        bags.backTrack(0);
        long endTime1=System.nanoTime(); //获取结束时间
        System.out.println("程序运行时间： "+(endTime1-startTime1)+"ns"+"   ， "+(endTime1-startTime1)/1000000+"ms");
        System.out.println("该背包能够取到的最大价值为:"+bags.maxValue);
        System.out.println("取出的方法为:");
        for(int i : bags.bestWay)
            System.out.print(i+"  ");
    }
}
